/*
删除字符串中的所有相邻重复项，给出由小写字母组成的字符串S，
重复项删除操作会选择两个相邻且相同的字母，并删除他们。
在S上反复执行重复项删除操作，直到无法继续删除，在完成所有重复项删除操作后返回最终的字符串
答案保证唯一
*/
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
char* removeDuplicates(char* s) 
{  
    int len = strlen(s);
    if (s == NULL)
    {
        return NULL;
    }  
    if (len == 0) 
    {
        /* 空字符串直接返回 */
        return s; 
    }  
  
    /* 分配足够的空间来存储最终字符串 */   
    char * array = (char *)malloc(sizeof(array) * (len + 1));  
    if (!array) 
    {
        return NULL; // 内存分配失败 
    } 
    /* 最终字符串的索引 */ 
    int pos = -1;   
    for (int idx = 0; idx < len; idx++) 
    {  
        if (pos == -1 || s[idx] != array[pos]) 
        {  
            /* 将非重复字符复制到结果字符串 */
            pos++;
            array[pos] = s[idx];  
        }
        else
        {
            pos--;
        }
    }  
    array[pos + 1] = '\0'; // 添加字符串结束符 
    return array;  
}  
  
int main() 
{  
    char s[] = "abbbacaacd";  
    char * array = removeDuplicates(s);  
 
    printf("array: %s\n", array);  
    free(array); // 释放分配的内存  
    return 0;  
}